package com.LeeCode;

import java.util.Arrays;

/**
 * 按位或最大的最小子数组长度
 */

public class Code2411 {
    public static void main(String[] args) {
        int[] nums = {3, 1, 0, 2, 1};
        System.out.println(Arrays.toString(new Code2411().smallestSubarrays1(nums)));
    }

    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n], firstPos = new int[32];
        for (int i = n - 1; i >= 0; i--) {
            for (int index = 0; index < 32; index++) {
                if ((nums[i] >> index & 1) == 1)
                    firstPos[index] = i;
            }
            int maxPos = i;
            for (int index = 0; index < 32; index++) {
                maxPos = Math.max(maxPos, firstPos[index]);
            }
            ans[i] = maxPos - i + 1;
        }

        return ans;
    }

    public int[] smallestSubarrays1(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        ans[n - 1] = 1;
        if (n == 1) return ans;


        // 保证栈中至少有两个数，方便判断窗口右端点是否要缩小
        nums[n - 1] |= nums[n - 2];
        int leftOr = 0, right = n - 1, bottom = n - 2;
        for (int left = n - 2; left >= 0; left--) {
            leftOr |= nums[left];
            // 子数组 [left,right] 的或值 = 子数组 [left,right-1] 的或值，说明窗口右端点可以缩小
            while (right > left && (leftOr | nums[right]) == (leftOr | nums[right - 1])) {
                right--;
                // 栈中只剩一个数
                if (bottom >= right) {
                    // 重新构建一个栈，栈底为 left，栈顶为 right
                    for (int i = left + 1; i <= right; i++) {
                        nums[i] |= nums[i - 1];
                    }
                    bottom = left;
                    leftOr = 0;
                }
            }
            ans[left] = right - left + 1;
        }
        return ans;
    }
}
